class Solution {
//思路来自：
    /*   作者：liweiwei1419
    链接：https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/

    public List<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<>();

        //这个递归函数的第四个参数 res，为啥必须设置呢？
        //原因是为了满足递归的条件：4、递归不要受外部因素影响。
        /*
            关于条件4 ：递归不要受外部因素影响 的解释：意思就是你不要在递归函数外部定义一个全局变量，或者一个全局数组。然后递归函数内部操作这个全局变量和数组。
            这种行为破坏了“能够放心大胆地将递归栈的中间部分当做开始部分”的性质，也破坏了递归的抽象归纳函数功能。**你把它放在递归函数入参里不香吗。。
        */
        dfs("",0,0,res,n);
        return res;
    }

    /**
     * @param curStr 当前递归得到的结果
     * @param left   左括号使用了几个
     * @param right  右括号使用了几个
     * @param res    结果集
     * @param n      题设需要生成的括号数量
     */
    private void dfs(String curStr, int left, int right, List<String> res, int n){
        //先编写递归结束条件!!!
        if (right > left){ //右括号大于左括号的使用
            return;
        }
        if (left > n){  //左括号大于n
            return;
        }

        if (left == n && right == n){   //添加符合条件的串
            res.add(curStr);
        }

        dfs(curStr+"(",left+1,right,res,n);
        dfs(curStr+")",left,right+1,res,n);
    }
}





